|
In mathematics elliptic curve primality testing techniques are among the quickest and most widely used methods in primality proving. It is an idea forwarded by Shafi Goldwasser and Joe Kilian in 1986 and turned into an algorithm by A. O. L. Atkin the same year. The algorithm was altered and improved by several collaborators subsequently, and notably by Atkin and , in 1993.〔Top, Jaap, ''Elliptic Curve Primality Proving'', http://www.math.rug.nl/~top/atkin.pdf〕 The concept of using elliptic curves in factorization had been developed by H. W. Lenstra in 1985, and the implications for its use in primality testing (and proving) followed quickly. Primality testing is a field that has been around since the time of Fermat, in whose time most algorithms were based on factoring, which become unwieldy with large input; modern algorithms treat the problems of determining whether a number is prime and what its factors are separately. It became of practical importance with the advent of modern cryptography. Although many current tests result in a probabilistic output (''N'' is either shown composite, or probably prime, such as with the Baillie–PSW primality test or the Miller–Rabin test), the elliptic curve test proves primality (or compositeness) with a quickly verifiable certificate.〔Atkin, A.O.L., Morain, F., ''Elliptic Curves and Primality Proving'', http://www.iai.uni-bonn.de/~adrian/ecpp/1992-atkin-morain-elliptic.pdf〕 Elliptic curve primality proving provides an alternative to (among others) the Pocklington primality test, which can be difficult to implement in practice. The elliptic curve primality tests are based on criteria analogous to the Pocklington criterion, on which that test is based,〔Washington, Lawrence C., Elliptic Curves: Number Theory and Cryptography, Chapman & Hall/CRC, 2003〕 where the group is replaced by , and ''E'' is a properly chosen elliptic curve. We will now state a proposition on which to base our test, which is analogous to the Pocklington criterion, and gives rise to the Goldwasser–Kilian–Atkin form of the elliptic curve primality test. ==Elliptic curve primality proving== It is a general-purpose algorithm, meaning it does not depend on the number being of a special form. ECPP is currently in practice the fastest known algorithm for testing the primality of general numbers, but the worst-case execution time is not known. ECPP heuristically runs in time: : for some . This exponent may be decreased to for some versions by heuristic arguments. ECPP works the same way as most other primality tests do, finding a group and showing its size is such that is prime. For ECPP the group is an elliptic curve over a finite set of quadratic forms such that is trivial to factor over the group. ECPP generates an Atkin–Goldwasser–Kilian–Morain certificate of primality by recursion and then attempts to verify the certificate. The step that takes the most CPU time is the certificate generation, because factoring over a class field must be performed. The certificate can be verified quickly, allowing a check of operation to take very little time. As of September 2015, the largest prime〔Caldwell, Chris. (The Top Twenty: Elliptic Curve Primality Proof ) from the Prime Pages.〕 that has been proved with ECPP method is the 30,950-digits value of the Lucas sequence term: The certification by Paul Underwood took 9 months using Marcel Martin's Primo software. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Elliptic curve primality」の詳細全文を読む スポンサード リンク
|